#include <string.h>
#include <stdio.h>
#include "calc.h"

#define ONES32 (((uint64_t)1 << 32) - 1)

void bi_plus(big_integer *r, const big_integer *a, const big_integer *b) {
	static big_integer t;
	clear_big_integer(&t);
	for (int i = 0; i < NUM_DIGITS; ++i) {
		t.digits[i] += (a->digits[i] + b->digits[i]);
		if (t.digits[i] > ONES32) {
			if (i < NUM_DIGITS - 1) {
				++t.digits[i + 1];
			}
			t.digits[i] &= ONES32;
		}
	}
	memcpy(r, &t, sizeof(big_integer));
}

void bi_minus(big_integer *r, const big_integer *a, const big_integer *b) {
	static big_integer t;
	clear_big_integer(&t);
	for (int i = 0; i < NUM_DIGITS; ++i) {
		t.digits[i] += (a->digits[i] - b->digits[i]);
		if (t.digits[i] > ONES32) {
			if (i < NUM_DIGITS - 1) {
				--t.digits[i + 1];
			}
			t.digits[i] += (ONES32 + 1);
		}
	}
	memcpy(r, &t, sizeof(big_integer));
}

void bi_mul(big_integer *r, const big_integer *a, const big_integer *b) {
	static big_integer t;
	clear_big_integer(&t);
	for (int i = 0; i < NUM_DIGITS; ++i) {
		uint64_t *rd = t.digits + i;
		for (int j = 0; i + j < NUM_DIGITS; ++j) {
			rd[j] += a->digits[i] * b->digits[j];
			if (i + j < NUM_DIGITS - 1) {
				rd[j + 1] += (rd[j] >> 32);
			}
			rd[j] &= ONES32;
		}
	}
	memcpy(r, &t, sizeof(big_integer));
}

void bi_div(big_integer *q, big_integer *r, const big_integer *a, const big_integer *b) {
	static big_integer t, s, cur;
	if (bi_cmp(a, b) < 0) {
		if (r) {
			memcpy(r, a, sizeof(*a));
		}
		if (q) {
			clear_big_integer(q);
		}
		return;
	}
	clear_big_integer(&t);
	memcpy(&s, a, sizeof(s));

	int bits_a = get_bits(a);
	int bits_b = get_bits(b);
	clear_big_integer(&cur);
	int i = bits_a - bits_b;
	set_bit(&cur, i);
	bi_mul(&cur, &cur, b);
	for (; i >= 0; --i) {
		if (bi_cmp(&s, &cur) >= 0) {
			set_bit(&t, i);
			bi_minus(&s, &s, &cur);
		}
		bi_shr1(&cur, &cur);
	}


	if (q) {
		memcpy(q, &t, sizeof(t));
	}
	if (r) {
		memcpy(r, &s, sizeof(s));
	}
}

void bi_mmul(big_integer *r, const big_integer *a, const big_integer *b, const big_integer *m) {
	static big_integer t;
	bi_mul(&t, a, b);
	bi_div(NULL, &t, &t, m);
	memcpy(r, &t, sizeof(t));
}

void bi_mpow(big_integer *r, const big_integer *a, const big_integer *b, const big_integer *m) {
	static big_integer t;
	clear_big_integer(&t);
	t.digits[0] = 1;
	for (int i = NUM_DIGITS - 1; i >= 0; --i) {
		for (int j = 31; j >= 0; --j) {
			bi_mmul(&t, &t, &t, m);
			if (b->digits[i] >> j & 1) {
				bi_mmul(&t, &t, a, m);
			}
		}
	}
	memcpy(r, &t, sizeof(t));
}

void bi_shr1(big_integer *r, const big_integer *a) {
	for (int i = 0; i < NUM_DIGITS; ++i) {
		r->digits[i] = a->digits[i] >> 1;
		if (i < NUM_DIGITS - 1) {
			r->digits[i] |= ((a->digits[i + 1] & 1) << 31);
		}
	}
}

int bi_cmp(const big_integer *a, const big_integer *b) {
	for (int i = NUM_DIGITS - 1; i >= 0; --i) {
		if (a->digits[i] < b->digits[i]) {
			return -1;
		}
		if (a->digits[i] > b->digits[i]) {
			return 1;
		}
	}
	return 0;
}

int bi_cmp_equal(const big_integer *a, uint32_t num) {
	if (a->digits[0] != (uint64_t)num) {
		return 1;
	}
	for (int i = 1; i < NUM_DIGITS; ++i) {
		if (a->digits[i] != 0) {
			return 1;
		}
	}
	return 0;
}
